#pragma once

#include <cassert>

namespace jianzhi_052
{

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int len_a = 0;
        for (auto node = headA; node != nullptr; node = node->next)
            ++len_a;

        int len_b = 0;
        for (auto node = headB; node != nullptr; node = node->next)
            ++len_b;

        while (len_a > len_b) {
            headA = headA->next;
            --len_a;
        }

        while (len_a < len_b) {
            headB = headB->next;
            --len_b;
        }

        assert(len_a == len_b);

        while (headA != nullptr) {
            if (headA == headB)
                return headA;
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
};

}  /* namespace jianzhi_052 */
